Semiconductor integrated circuits often include large trees of combinational logic gates for reducing a large number of data bits into a smaller number of bits, such as a single bit, according to some logical function. Some logic trees apply a singular logical function to an entire data word such that the same function is applied to all bits in the incoming data word. This type of function can be referred to as a “word-wise” logical function. Examples of typical word-wise logical functions include AND, NAND, OR, NOR, XOR and XNOR functions.
As the sizes of transistors continue to become smaller with new fabrication technologies, the voltage supply levels that drive the transistors are also reduced to prevent damage to the small transistors. This limits the number of transistors that can be connected together in series to perform a logical function, such as an AND, and hence the maximum number of inputs to each logic gate. This number is based on the magnitude of the supply voltage and the voltage drop across each transistor. For example, a given semiconductor technology may limit the number of inputs to a logic AND gate to three bits.
This significantly increases the complexity of reduction circuits having a large number of input bits since small groups of bits must be combined in multiple logic levels. If the maximum number of inputs to a logic AND gate is three bits, then a word-wise AND of a 16-bit data word would require three logic levels. The first logic level could include six 3-input AND gates to logically AND six groups of three bits. The second logic level could include two 3-input AND gates to logically AND the outputs from the first level. Finally, the third logic level could include an additional AND gate to logically AND the outputs from the second level.
The complexity of the logic trees significantly increases with the number of input bits and with more complex logical functions such as XOR and XNOR. Large Boolean logic reduction trees therefore typically consume a large area on the integrated circuit and a relatively large amount of power and can have long critical path propagation delays.
Simplified logic reduction trees are therefore desired for performing arbitrary word-wise reduction functions in a tree structure.